import java.util.ArrayList;

/**
 * Copyright (C) 2002 Michael Green <mtgreen@cs.ucsd.edu>
 * 
 * Copyright (C) 2002 Paul Kube <kube@cs.ucsd.edu>
 * 
 * Copyright (C) 2005 Owen Astrachan <ola@cs.duke.edu>
 * 
 * Copyright (C) 2011 Hoa Long Tam <hoalong.tam@berkeley.edu> and Armin Samii
 * <samii@berkeley.edu>
 * 
 * This file is part of CS Boggle.
 * 
 * CS Boggle is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
 * CS Boggle is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * CS boggle. If not, see <http://www.gnu.org/licenses/>.
 */

public class AutoPlayerBoardFirst extends AbstractPlayer {

	public AutoPlayerBoardFirst(LexiconInterface lex) {
		this.initialize(lex);
	}

	/**
	 * Find all the valid words automatically, found words should be added via the
	 * <code>AbstractPlayer</code>'s <code>add</code> method.
	 * 
	 * @param board
	 *          is the BoggleBoard on which words are found
	 * @param lex
	 *          is the lexicon in which words are searched/validated
	 * @param minLength
	 *          of words found by an autoplayer
	 */

	public void findAllValidWords(BoggleBoard board, LexiconInterface lex, int minLength) {
		//System.out.println("NEW GUESS");
		ArrayList<String> wordsToAdd;
		BoardCell startingCell;
		for (int x = 0; x < board.size(); x++) {
			for (int y = 0; y < board.size(); y++) {
				startingCell = new BoardCell(x, y);
				boardTree myBoardTree = new boardTree(startingCell, board, lex); 
				myBoardTree.addNeighbors(myBoardTree.myRoot);
				//myBoardTree.print(myBoardTree.myRoot);
				wordsToAdd = myBoardTree.getWords();
				//System.out.println("Size of list: " + wordsToAdd.size());
				while (!wordsToAdd.isEmpty()) {
					if (wordsToAdd.get(0).length() >= minLength) {
						this.add(wordsToAdd.get(0));
						wordsToAdd.remove(0);
					} else {
						//System.out.println(wordsToAdd.get(0));
						wordsToAdd.remove(0);
					}
				}
			}
		}
	}

	private class boardTree {
		boardTreeNode myRoot;
		BoggleBoard myBoard;
		LexiconInterface myLex;
		ArrayList<String> myWords;

		//constructor, populate tree
		public boardTree(BoardCell cell, BoggleBoard board, LexiconInterface lex) {
			myRoot = new boardTreeNode(cell);
			myBoard = board;
			myLex = lex;
			myWords = new ArrayList<String>();
		}

		public void print(boardTreeNode node) {
			if (!node.myNeighbors.isEmpty()) {
				System.out.print("Node: " + toString(node.myItem) + "//Neighbors: "); //print parent node
				for (int i = 0; i < node.myNeighbors.size(); i++) {
					System.out.print(toString(node.myNeighbors.get(i).myItem) + " ");
				}
				System.out.println();
				for (int i = 0; i < node.myNeighbors.size(); i++) {
					print(node.myNeighbors.get(i));
				}
			} 
		}

		public ArrayList<String> getWords () {
			return myWords;
		}

		public void addNeighbors(boardTreeNode current) {
			for (int x = current.myItem.col - 1; x <= current.myItem.col + 1; x++) {
				if (x < 0 || x > myBoard.size() - 1) {
					continue;
				} else {
					for (int y = current.myItem.row - 1; y <= current.myItem.row + 1; y++) {
						if (y < 0 || y > myBoard.size() - 1) {
							continue;
						} else {
							//if what we have so far + the new neighbor isn't in the prefix for a word, don't add it------------
							String myStr = getString(current, new BoardCell(y, x));
							if (myLex.containsPrefix(myStr) || myLex.contains(myStr)) {
								if (current.addNeighbor(new BoardCell(y, x))) { //try to add it, still not guaranteed to be valid (performance fix here)
									//if its a word, add it to our word list
									if (myLex.contains(myStr)) {
										myWords.add(myStr); //could potentially add the same word twice
									}
								}
							}
						}
					}
				}
			}
			//recurse
			for (int i = 0; i < current.myNeighbors.size(); i++) {
				this.addNeighbors(current.myNeighbors.get(i));
			}
		}
		//given a node and a current cell, return the combined string up until that point
		private String getString(boardTreeNode node, BoardCell cell) {
			String str = "";
			for (int i = 0; i < node.visited.size(); i++) {
				str += myBoard.getFace(node.visited.get(i).row, node.visited.get(i).col);
			}
			str += myBoard.getFace(node.myItem.row, node.myItem.col);
			str += myBoard.getFace(cell.row, cell.col);
			return str;

		}

		private String toString(BoardCell cell) {
			return myBoard.getFace(cell.row, cell.col);
		}

		public class boardTreeNode {
			BoardCell myItem;
			ArrayList<boardTreeNode> myNeighbors; //current neighbors of this node
			ArrayList<BoardCell> visited; //array list of currently visited nodes in this path

			//Constructor
			public boardTreeNode(BoardCell item) {
				myItem = item;
				visited = new ArrayList<BoardCell>();
				myNeighbors = new ArrayList<boardTreeNode>();
			}
			public boolean addNeighbor(BoardCell neighbor) {
				//if the cell is a neighbor, add it to our myNeighbors arraylist
				if (myItem.isNeighbor(neighbor)) {//neighbor.isNeighbor(myItem)) {
					//if our current history doesn't contain the neighbor, then add it
					if (!visited.contains(neighbor)) {
						boardTreeNode addMe = new boardTreeNode(neighbor);
						//update the history of the new node
						for (int i = 0; i < visited.size(); i++) {
							addMe.visited.add(visited.get(i));
						}
						addMe.visited.add(myItem);
						myNeighbors.add(addMe);
						return true;
					}
				}
				return false;
			}
		}
	}

	@Override
	public String getName() {
		return "AutoPlayer";
	}
}
